#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include<stdio.h>
int GetMid(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[mid] > a[begin])
	{
		if (a[mid] < a[end])
			return mid;
		else if (a[begin] > a[end])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}
void swap(int* a1, int* a2)
{
	int temp = *a1;
	*a1 = *a2;
	*a2 = temp;
}
int PartSort3(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[mid], &a[begin]);
	int prev = begin, cur = begin + 1;
	int key = a[begin];
	while (cur <= end)
	{
		if (a[cur] < key)
		{
			prev++;
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	a[begin] = a[prev];
	a[prev] = key;
	return prev;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}
int main()
{
	int a[] = { 5,3,6,7,2,8,1,2 };
	int n = sizeof(a) / sizeof(int);
	QuickSort(a, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}